Routing and Wavelength Assignment (RWA) is a well-known problem for fixed grid optical networks while Routing and Spectrum Assignment (RSA) is its equivalent term to the same problem for flexible grid optical networks. In fixed grid optical networks, wavelengths are spaced apart from each other according to a wavelength spectrum grid defined by International Telecommunication Union (ITU) in ITU-T G.694.1 (02/12), “Spectral grids for WDM applications: DWDM frequency grid,” the contents of which are incorporated by reference. In flexible grid optical networks, which is also described in ITU Recommendation G.694.1 “Spectral grids for WDM applications: DWDM frequency grid” (02/12), each signal can be allocated to spectrum with different spectral widths optimized for the bandwidth requirements of the particular bit rate and modulation scheme of the individual channels. The ultimate objective of RWA or RSA is to find a wavelength or spectrum assignment on a route for a particular channel in the optical network, such assignment and routing being optimal in some manner.
The conventional implementation for Spectrum Assignment (SA) techniques utilizes a sequential processor which handles requests one at a time. This approach attempts to optimize the current spectrum planning foreach new request which attempts to achieve a local optimization. However, a current request can block network resources for subsequent requests, i.e., the sequence of requests that is provided to an SA engine has a significant impact on the final resultant spectrum plan. As there can be almost an infinite number of request sequence orders as an input, SA planning results vary significantly.
There are some crude heuristics for sorting the (demand) list of requests before assigning them sequentially. For example, a “Longest first” selection criteria is commonly used which is believed to lead to better spectrum assignment than random ordering. In this approach, the ordering of the (demands) requests is done based on the network resources that they will consume, e.g., on the number of hops they traverse. The original problem is O(NN) and classified as Discrete Optimization (DOP) of Binary Integer Linear Programming (BILP). A branch and bound technique is the only systematic solution for these types of problems.
The problems with the ILP approach for SA include processing time and scalability. For processing time, conventional approaches with ILP can vary from hours to days depending on the network topology or specifically on the number of Optical Multiplex Sections (OMS) or fibers and the number of service demands. For scalability, the processing time does not have a linear relationship with either the number of OMS sections or the number of service demands; rather the relationship is typically exponential. The conventional SA techniques that use a sequential approach and develop a methodology for sorting the demand services in an ordered list based on some certain criteria suffer from flexibility issues as the rules which govern this sorting process vary with the change of network topology, type of the service demands and the number of service demands. A branch and bound technique suffers from computational complexity in terms of running time and memory size required. The nature of SA is a Non-deterministic Polynomial-Time (NP)-hard problem, and a globally optimal solution is not achievable. Accordingly, heuristic approaches are better suited for SA.